1. Technical Field
The present invention relates generally to the field of computer software and more specifically to managing disk drive linking through the use of hash tables.
2. Description of Related Art
Computers utilize a wide variety of memory devices to store data. One generic type of memory device is typically referred to as a disk. Disks are classified according to the storage medium employed, such as an xe2x80x9copticalxe2x80x9d disk or a xe2x80x9cmagneticxe2x80x9d disk. Disks are also generally classified as either xe2x80x9cfloppyxe2x80x9d or xe2x80x9chard.xe2x80x9d Hard disks generally have greater storage capacity, faster data access times, and longer useful lives than floppy disks. However, unlike hard disks, floppy disks are removable and portable. That is floppy disks are easily released from, and reattached to, a disk drive, which provides the computer with access to the data on the disk.
Disks are physically divided up into heads, cylinders, and sectors. Although a sector may be identified by specifying a head, a cylinder, and a sector within the cylinder, a sector may also be identified by a xe2x80x9clogical sector address.xe2x80x9d Each logical sector address is a single number rather than a triplet of numbers. The logical address of a sector corresponds to the number of sectors between the addressed sector and the xe2x80x9cfirstxe2x80x9d sector on the disk along some specified path which traverses all available sectors in order. The first sector is usually known as xe2x80x9csector zero.xe2x80x9d
Disks are also classified by rules governing the physical organization of data on the disk. Many disks mold the available space into one or more xe2x80x9cpartitionsxe2x80x9d by a xe2x80x9cpartition tablexe2x80x9d located on the disk. The partition table includes partition identifiers. Each partition identifier includes a starting address, which is the physical sector address of the first sector in the partition in question, and an ending address, which is the physical sector address of the last sector in the partition. These partitions may be linked together to provide a unified storage mechanism for the host computer or network.
Sometimes, more than one drive is linked together to provide storage to a computer or a network of computers. A drive linking algorithm maintains a list of the drives and/or partitions being linked. When an input/output request is received, this list is searched sequentially to determine which drive (or partition) the input/output request is to be routed to. If an input/output request crosses a boundary (i.e. part of the input/output request needs to be routed to one drive (or partition) and part of the input/output request needs to be routed to a second drive (or partition)), the input/output request must be broken up into two (or more) requests. As the average number of links in the list increases, the average performance of the linked entity as a whole decreases, and data written to and read from drives (or partitions) which appear later in the list occurs slower than for drives (or partitions) which appear earlier in the list. Therefore, it is desirable to have a method of linking drives and/or partitions that stabilizes access to the drives and/or partitions such that the performance of the system is constant regardless of the number of drives and/or partitions being linked without having to place any restrictions on the size or number of drives and/or partitions being linked.
The present invention provides a method for routing an input/output request for a particular logical volume. In a preferred embodiment, partitions are assigned to logical volumes, wherein an arbitrary number of partitions can be assigned to a logical volume and the partitions can be of an arbitrary size. Each logical volume is divided into a plurality of zones, wherein the zones for a particular logical volume are substantially equal in size. A zone table is created, whose entries contain data about one or two partitions that correspond to that zone. Responsive to receiving an input/output request directed to a logical volume, the zone table entries for a first and a last sector listed in the input/output request are used to determine to which partitions in the logical volume the input/output request should be routed.